package cn.edu.besti.cs1723.Z2316;

import week3rd.LinkedQueue;
import week9th.jsjf.ArrayHeap;

import java.util.ArrayList;
import java.util.Stack;

public class HuffmanTree
{
    private HuffmanTreeNode Root;	// 根结点
    private String[] codes = new String[28];

    public HuffmanTree(HuffmanTreeNode[] array) {
        HuffmanTreeNode parent = null;
        ArrayHeap<HuffmanTreeNode> heap = new ArrayHeap();
        for (int i=0;i<array.length;i++)
        {
            heap.addElement(array[i]);
        }

        for(int i=0; i<array.length-1; i++) {
            HuffmanTreeNode left = heap.removeMin();  // 最小节点是左孩子
            HuffmanTreeNode right = heap.removeMin();


            parent = new HuffmanTreeNode(left.getWeight()+right.getWeight(),' ',null,left,right);
            left.setParent(parent);
            right.setParent(parent);

            heap.addElement(parent);
        }

        Root = parent;
    }
    public String toString()
    {
        LinkedQueue<HuffmanTreeNode> nodes =
                new LinkedQueue<>();
        LinkedQueue<Integer> levelList =
                new LinkedQueue<>();
        HuffmanTreeNode current;
        String result = "";
        int printDepth = this.getHeight()-1;
        int possibleNodes = (int)Math.pow(2, printDepth + 1);
        int countNodes = 0;

        nodes.enqueue(Root);
        Integer currentLevel = 0;
        Integer previousLevel = -1;
        levelList.enqueue(currentLevel);

        while (countNodes < possibleNodes)
        {
            countNodes = countNodes + 1;
            current = nodes.dequeue();
            currentLevel = levelList.dequeue();
            if (currentLevel > previousLevel)
            {
                result = result + "\n\n";
                previousLevel = currentLevel;
                for (int j = 0; j < ((Math.pow(2, (printDepth - currentLevel))) - 1); j++)
                    result = result + " ";
            }
            else
            {
                for (int i = 0; i < ((Math.pow(2, (printDepth - currentLevel + 1)) - 1)) ; i++)
                {
                    result = result + " ";
                }
            }
            if (current != null)
            {
                result = result + current.getWeight();
                nodes.enqueue(current.getLeft());
                levelList.enqueue(currentLevel + 1);
                nodes.enqueue(current.getRight());
                levelList.enqueue(currentLevel + 1);
            }
            else {
                nodes.enqueue(null);
                levelList.enqueue(currentLevel + 1);
                nodes.enqueue(null);
                levelList.enqueue(currentLevel + 1);
                result = result + " ";
            }
        }
        return result;
    }
    public int getHeight()
    {
        return height(Root);
    }


    private int height(HuffmanTreeNode node)
    {
        if(node==null){
            return 0;
        }
        else {
            int leftTreeHeight = height(node.getLeft());
            int rightTreeHeight= height(node.getRight());
            return leftTreeHeight>rightTreeHeight ? (leftTreeHeight+1):(rightTreeHeight+1);
        }
    }


    protected void inOrder( HuffmanTreeNode node,
                            ArrayList<HuffmanTreeNode> tempList)
    {
        if (node != null)
        {
            inOrder(node.getLeft(), tempList);
            if (node.getElement()!=' ')
                tempList.add(node);

            inOrder(node.getRight(), tempList);
        }
    }

    public String[] getEncoded() {
        ArrayList<HuffmanTreeNode> arrayList = new ArrayList();
        inOrder(Root,arrayList);
        int x = 0;
        for (int i = 0; i < arrayList.size(); i++)
        {
            HuffmanTreeNode node = arrayList.get(i);
            String result ="";
            if (x - 'a' == -65)
                x = 27;
            else if (x - 'a' == -53)
                x = 28;
            else
                x = node.getElement() - 'a';
            Stack stack = new Stack();
            while (node!=Root)
            {
                if (node==node.getParent().getLeft())
                    stack.push(0);
                if (node==node.getParent().getRight())
                    stack.push(1);

                node=node.getParent();
            }
            while (!stack.isEmpty())
            {
                result +=stack.pop();
            }
            codes[x] = result;
        }

        return codes;
    }

    public HuffmanTreeNode getRoot() {
        return Root;
    }
}
